#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: n_queue.py 
@version:
@time: 2024/01/24

棋盘上如何放置棋子本身就是一种试探行为

由于最终需要输出所有放置方案，因此需要借助一个列表rec来表示每一行中皇后的位置，第1行中皇后放置在第rec[1]列，初始化时rec中所有值为正无穷。

通过一个judge函数判断前后放置是否冲突

当x1+y1与x2+y2相等时，说明处于同一负对角线，当|x1-y1|与|x2-y2|相等说明在同一对角线

接下来，考虑如何深度优先搜索和回溯。

判断第i行的皇后位置时，对列进行遍历，判断可以将皇后放置在哪一列，找到可放置的位置之后，更新rec列表，然后增大行数为i+1，
继续递归深入。当递归深入找不到结果时，就将rec值退回执行之前，继续对第i行皇后放在哪一列进行遍历。如此一来，我们就理清了递归函数的内部逻辑。
"""


class Solution:
    re = []
    rec = []

    def n_queue(self, n):
        self.re = []
        self.rec = [float('inf') for _ in range(n)]
        self.dfs(n, 0)
        return self.re

    def dfs(self, n, row):
        if row == n:
            self.figure(n)
        for col in range(n):
            if self.judge(row, col):
                self.rec[row] = col
                self.dfs(n, row + 1)
                self.rec[row] = float('inf')

    def figure(self, n):
        output = []
        for i in range(len(self.rec)):
            stri = '.' * self.rec[i] + 'Q' + '.' * (n - self.rec[i] - 1)
            output.append(stri)
        self.re.append(output)

    def judge(self, row, col):
        for i in range(len(self.rec)):
            if self.rec[i] - i == col - row or self.rec[i] + i == col + row or self.rec[i] == col:
                return False
        return True


print(Solution().n_queue(4))
